package __二叉树

/*
*
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

根据前序+中序, 重建二叉树

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
*/
var (
	hash105 map[int]int //全局map
)

func buildTree105(preorder []int, inorder []int) *TreeNode {
	hash105 = make(map[int]int, len(inorder))
	for i, v := range inorder { //遍历中序数组, 存储值-下标
		hash105[v] = i
	}

	//调用重构方法  preorder:前序数组 inorder:中序数组 root:节点下标  l:左节点下标  r:右节点下标
	root := build(preorder, inorder, 0, 0, len(inorder)-1) // l, r 表示构造的树在中序遍历数组中的范围
	return root
}

func build(pre []int, in []int, rPreIndex int, l, r int) *TreeNode {
	//如果左指针 > 右指针,直接返回
	if l > r {
		return nil
	}

	rVal := pre[rPreIndex]       // 找到本次构造的树的根节点
	rInIndex := hash105[rVal]    // 根节点在中序数组中的位置
	node := &TreeNode{Val: rVal} //构造为根节点

	/*
			前序 [根 * * * * * * * * * * ]
			中序 [* * * * 根 * * * * * * ]
		 				  4
	*/
	node.Left = build(pre, in, rPreIndex+1, l, rInIndex-1)               //传入前序数组,中序数组, rPreIndex+1:前序根节点下标右移一位 l:中序的左边界 rInIndex-1:本地中序根节点位置-1
	node.Right = build(pre, in, rPreIndex+(rInIndex-l)+1, rInIndex+1, r) //传入前序,中序数组,

	return node
}
